package BinaryTree;
import java.util.LinkedList;
import java.util.Queue;


//二叉树的完全性检验: https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/
//时间复杂度: O(n)
public class CompleteTree {
	
	public static int MAXN=101;
	public static TreeNode[] queue=new TreeNode[MAXN];
	//记录节点编号的数组
	public static int[] pos=new int[MAXN];
	public static int l,r;
	
	//树的一个特性： 编号，知道1个编号就可以指定孩子的编号 =》 只要编号不连续就不是完全二叉树
	public boolean isCompleteTree3(TreeNode root) {
		l=r=0;
		queue[r]=root;
		pos[r++]=1;
		int prevIndex=0;
		while(l<r) {
			TreeNode cur=queue[l];
			int index=pos[l++];
			if(index!=prevIndex+1) {
				return false;
			}
			prevIndex=index;
			if(cur.left!=null) {
				queue[r]=cur.left;
				pos[r++]=2*index;
			}
			if(cur.right!=null) {
				queue[r]=cur.right;
				pos[r++]=2*index+1;
			}
		}
		return true;
	}
	
	
	//数组模型队列
	public boolean isCompleteTree2(TreeNode root) {
		l=r=0;
		boolean leaf=false;
		queue[r++]=root;
		while(l<r) {
			TreeNode cur=queue[l++];
			//不是完全二叉树的情况：
			//  1.左孩子为空，但右孩子不为空   2.左空右不空，后面节点一定要是叶子节点
			if((cur.left==null&&cur.right!=null)||(leaf&&(cur.left!=null||cur.right!=null))) {
				return false;
			}
			if(cur.left!=null) {
				queue[r++]=cur.left;
			}
			if(cur.right!=null) {
				queue[r++]=cur.right;
			}
			if(cur.left==null||cur.right==null) {
				leaf=true;
			}
		}
		return true;
	}
	
	//使用队列接口来进行判断
	public boolean isCompleteTree1(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean leaf=false;
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if((cur.left==null&&cur.right!=null)||(leaf&&(cur.left!=null||cur.right!=null))){
                return false;
            }
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if(cur.right!=null){
                queue.add(cur.right);
            }
            if(cur.left==null||cur.right==null){
                leaf=true;
            }
        }
        return true;
    }
}
